/**
 * 常规二叉树遍历的问题
 * 1. 栈和队列需要的春初空间很大
 * 2. 任意一棵二叉树往往存在大量的空指针。例如，拥有n个节点的二叉树有n+1个空指针，它们占用的空间被浪费了
 * 3. 很难直接找到一个给定节点的后记节点（前序、中序和后续后继）
 * 线性二叉树的类型
 * 1. 前序线索二叉树：空左指针存储前序序列前驱信息，空右指针将存储前序序列后继信息
 * 2. 中序线索二叉树：空左指针存储中序序列前驱信息，空右指针将存储中序序列后继信息
 * 3. 后续线索二叉树：空左指针存储后序序列前驱信息，空右指针将存储后序序列后继信息
 *                          A
 *                        /   \
 *                       B     C
 *                      / \    /
 *                     D   E  F
 * 前序遍历：ABDECF
 * 中序遍历：DBEAFC
 * 后序遍历：DEBFCA
*/
typedef struct ThreadedBinaryTreeNode
{
    ThreadedBinaryTreeNode* left;
    ThreadedBinaryTreeNode* right;
    const char* data;
    int lTag;
    int rTag;
} ThreadedBinaryTreeNode;

class ThreadedBinaryTree {
private:
    int mode;
    ThreadedBinaryTreeNode* root;
public:
    ThreadedBinaryTree(int mode, const char* rootData);
    // 在中序线索二叉树中查找中序后继
    ThreadedBinaryTreeNode* inorderSuccessor(ThreadedBinaryTreeNode* p);
    //插入节点
    ThreadedBinaryTreeNode* insertNode(const char* data);
    //中序索引二叉树的中序遍历
    void inorderTaversal();
    ThreadedBinaryTreeNode* getRootNode();
};